package com.huawei.M01.iterator.M21;

import java.util.ArrayList;
import java.util.List;

/**
 *93. 复原 IP 地址
 *
 * @author 11
 */
public class IpAddress {
    public static final int Max_SIZE = 4;
    public static final String ZERO = "0";
    public static final String POINT = ".";
    List<String> res = new ArrayList<>();
    private int[] ans = new int[Max_SIZE];
    public List<String> restoreIpAddresses(String s) {
        dfs(s, 0, 0);
        return res;
    }

    private void dfs(String s, int index, int startIndex) {
        // 递归头
        if (index == Max_SIZE ) {
            if (startIndex == s.length()) {
                StringBuilder sb = new StringBuilder(7);
                for (int i = 0; i < Max_SIZE; i++) {
                    sb.append(ans[i]);
                    if (i < Max_SIZE - 1) {
                        sb.append(POINT);
                    }
                }
                res.add(sb.toString());
            }
            return;
        }
        // 如果提前达到四个，直接返回，回溯
        if (startIndex == s.length()) {
            return;
        }
        // 处理起始位为0
        if (s.charAt(startIndex) == '0') {
            ans[index] = 0;
            dfs(s, index + 1, startIndex + 1);
        }

        int num = 0;
        for (int start = startIndex; start < s.length(); start++) {
            num = num * 10 + (s.charAt(start) - '0');
            if (num > 0 && num <= 255) {
                ans[index] = num;
                dfs(s, index + 1, start + 1);
            }else {
                break;
            }
        }

    }

    public static void main(String[] args) {
        System.out.println(new IpAddress().restoreIpAddresses("25525511135"));
    }
}
